1. Field of the Invention
The present invention generally relates to a memory device and an intermediary apparatus using the memory device and, more particularly, to an associative memory device and an intermediary apparatus using the associative memory device which receives a key that is input for retrieving data stored in a memory, and returns an address at which the key is stored.
2. Description of the Related Art
A CAM is used in an intermediary apparatus for a network, which is required to perform various searches, such as a destination search, a priority search and a filtering search. The CAM (Content Addressable Memory), i.e., an associative memory device, realizes a function of inputting data, which is stored in a memory (a CAM entry), as a key, and returning an address of the CAM entry at which the key is stored.
A function realized by a conventional CAM is receiving a search key as an input, and returning one address of a CAM entry which matches the key. Besides, when a plurality of CAM entries match the search key, normally only a lowest-numbered address is returned as a search result, although it is informed that the search key matches a plurality of the CAM entries.
Under this circumstance, a CAM is frequently used for searches, including a destination search, a priority control and a filtering, performed in an intermediary apparatus for a network, especially a router relaying an IP (Internet Protocol) packet, and a layer 2 switch switching a MAC (Media Access Control) frame of Ethernet prescribed by IEEE802.3 in a LAN (Local Area Network); when performing all these search processes by an existent CAM, each search is performed separately because only one search result can be returned for one search operation. In other words, a plurality of searches are performed for one frame or one packet.
Conventionally, for such reasons as a short search key length, inputting one search operation takes only a time of 1τ (τ represents one clock cycle). Recently, however, the search key length for a CAM has become increased as an intermediary apparatus for a network has become multifunctional, as a result of which a search key needs to be divided into a plurality of keys upon being input; therefore, inputting one search operation has come to take a time of nτ (n represents a number larger than 1). FIG. 1 shows a signal timing chart of an example in which one search input (a search instruction) takes 4τ because the search key is divided into four.
Accordingly, when a number of searches are performed to a same CAM, it takes {the time required for inputting one search operation} times {the number of the searches}; consequently, it is not practical to perform a number of searches in a single CAM because a search time is a vital factor in an intermediary apparatus dealing with an ultra high-speed line. FIG. 2 shows a signal timing chart of an example in which three searches are performed when one search input takes 4τ.
Alternatively, preparing one CAM exclusively for each of a plurality of searches, and executing a plurality of CAMs in parallel while each CAM performs one search, improves a performance thereof.
However, when a plurality of CAMs are mounted, control chips also need to be mounted so as to connect respective CAMs with one another; this increases a mounting area. Alternatively, when a plurality of CAMs are controlled by a single control chip, there also occurs a problem that the control chip requires an increased number of pins, and becomes complicated to control. Besides, in either method, the number of mounted chips becomes larger; this imposes a considerable disadvantage in pricing an apparatus on which the chips are mounted.
Besides, a description will be given, with reference to FIG. 3, of a conventional intermediary apparatus. This intermediary apparatus performs three searching processes regarding a destination, a flow type and a filtering. First, in a header analyzer 51, header information is extracted from each frame supplied via a port, and is attached to the frame.
Next, in a destination determiner 52, the header information is supplied to a destination information storage CAM 53 connected thereto so as to obtain destination information, and the destination information is attached to the frame. Subsequently, in a flow type determiner 54, the header information is supplied to a flow type storage CAM 55 connected thereto so as to obtain a flow type, and the flow type is attached to the frame. Subsequently, in a filtering processor 56, the header information is supplied to a filtering information storage CAM 57 connected thereto so as to obtain filtering information. In the filtering processor 56, when the filtering information indicates that the frame is to be filtered, the frame is discarded so that the frame is not to be relayed to a subsequent stage.
Further, in a queue controller 58 at the subsequent stage, a priority control is performed according to priority information indicated by the flow type attached to the frame. An in-apparatus switch 59 switches the frame to a destination indicated by the destination information attached to the frame. Besides, in an internal header remover 60 subsequent to the in-apparatus switch 59, the header information, the destination information and the flow type are detached from the frame, and the frame is transmitted via the port.
Thus, the conventional intermediary apparatus includes the destination information storage CAM 53, the flow type storage CAM 55 and the filtering information storage CAM 57 which are mounted thereon; and the conventional intermediary apparatus also needs to include control chips of the destination determiner 52, the flow type determiner 54 and the filtering processor 56 which control the respective CAMs. Consequently, the conventional intermediary apparatus has to have a large mounting area. Besides, even when these control chips are replaced with a single control chip controlling all of the above-mentioned CAMs, the single control chip needs to include interfaces with the respective CAMs. Thus, the number of pins required in the conventional intermediary apparatus is increased, imposing a considerable disadvantage on a cost of the conventional intermediary apparatus. Further, even with the single control chip, search processes are performed separately in the respective CAMs; thus, the mounting area is not decreased.